/*
1971.寻找图中是否存在路径  https://leetcode.cn/problems/find-if-path-exists-in-graph/
简单 2024/10/06
原先我是用dfs写的，但是在最后一个用例当n=100001时，运行超出时间限制，33/34个通过的测试用例
代码如下：
class Solution {
private:
    // 构建图的邻接表
    void buildGraph(vector<vector<int>>& edges, vector<vector<int>>& graph) {
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
    }
    // 深度优先搜索函数
    bool dfs(int cur, int destination, vector<bool>& visited, const vector<vector<int>>& graph) {
        if (cur == destination) return true;
        visited[cur] = true;
        for (int next : graph[cur]) {
            if (!visited[next]) {
                if (dfs(next, destination, visited, graph)) return true;
            }
        }
        return false;
    }
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // 构建图的邻接表
        vector<vector<int>> graph(n);
        buildGraph(edges, graph);
        // 记录顶点是否已被访问
        vector<bool> visited(n, false);
        return dfs(source, destination, visited, graph);
    }
};

下面是广度优先搜索，并用队列将已入队的元素标记为已访问，终于过了......
*/
class Solution {
private:
    void buildGraph(vector<vector<int>>& edges, vector<vector<int>>& graph) {
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
    }
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph(n);
        buildGraph(edges, graph);
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(source);
        visited[source] = true;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            if (cur == destination) return true;
            for (int next : graph[cur]) {
                if (!visited[next]) {
                    q.push(next);
                    visited[next] = true;
                }
            }
        }
        return false;
    }
};